#a:第一个柱子
#b:第二个柱子
#c:第三个柱子
def Hanoi(n, a,b,c):
	if (n == 1):
		print(a, "->", c)
	else:
		Hanoi(n-1,a,c,b)#将a柱子上的n-1个盘子移动到b柱子上
		Hanoi(1, a,b,c)#将a柱子上最后一个盘子移动到c柱子上
		Hanoi(n-1,b,a,c)#将b柱子上的n-1个盘子移动到c柱子上
Hanoi(3,"a","b","c")
 class SqStack:#定义栈类
    def __init__(self):#用数组替代栈
        self.data=[]
    def empty(self):#判空方法
        if len(self.data)==0:
            return True
        return False
 
    def push(self,e):#压栈方法，一个元素右压栈
        self.data.append(e)
 
    def pop(self):#出栈方法，判空后一个元素右出栈
        assert not self.empty()
        return self.data.pop()
 
    def gettop(self):#判空后获取栈顶元素
        assert not self.empty()
        return self.data[len(self.data)-1]
 
if __name__=='__main__':#主函数验证栈类
    st=SqStack()
    st.push(1)
    st.push(2)
    st.push(3)
    st.push(4)
    print("出栈顺序：",end=' ')
    while not st.empty():
        print(st.pop(),end=' ')
    print()
 class Question:#定义问题类
    def __init__(self,m,a,b,c,N):
        self.m=m
        self.a=a#开始
        self.b=b#借助
        self.c=c#目标
        self.N=N#递归树层数 #用堆栈（先进后出）
from SqStack import SqStack#导入自定义栈模块（注意得在同一包下才可以导入）
from Question import Question#导入自定义问题模块
def Hanoi(n):
    st=SqStack()#实例化栈
    p=Question(n,'a','b','c')
    st.push(p)#原始问题压栈
    while not st.empty():
        p=st.pop()#默认弹出栈顶元素
        if p.m==1:
            print("{}->{}".format(p.a,p.c))
        else:
            # 子问题压栈，由于先进后出，所以子问题应当以相反的顺序进栈
            b=Question(p.m-1,p.b,p.a,p.c)##将b柱子上的n-1个盘子移动到c柱子上
            st.push(b)
            b=Question(1,p.a,p.b,p.c)#将a柱子上最后一个盘子移动到c柱子上
            st.push(b)
            b=Question(p.m-1,p.a,p.c,p.b)#将a柱子上的n-1个盘子移动到b柱子上
            st.push(b)
n=eval(input("请输入汉诺塔的层数："))
Hanoi(n)